<<<<<<< HEAD:cxx/algorithm/src/kmp.cc
//
// Created by liushuai on 2020/4/29.
//
#include "kmp.h"

int* Next(std::string &pattern) {
    int pattern_length = static_cast<int>(pattern.length());
    int* n = new int[pattern_length+1];
    n[0] = -1;
    int j = 0, k = -1;
    while (j < pattern_length) {
        if (k == -1 || pattern[j] == pattern[k]) {
            ++j;
            ++k;
            n[j] = k;
        } else
            k = n[k];
    }
    return n;
}

int kmp(std::string target, std::string pattern) {
    int i = 0, k = 0;
    int target_length = target.length();
    int pattern_length = pattern.length();
    int* n = Next(pattern);
    // 无法比较-1和pattern_length长度
    while (i < target_length && k < pattern_length) {
        if (k == -1 || target[i] == pattern[k]) {
            i++;
            k++;
        } else
            k = n[k];
    }
    delete [] n;
    if (k == pattern.length())
        return i - k;
    else
        return -1;
}
=======
#include "kmp.h"

#include <iostream>
std::vector<int> getNext(std::string &pattern) {
  int i = 0, j = -1;
  std::vector<int> n = std::vector<int>(pattern.length(), -1);
  while (i < pattern.length()) {
    if (j == -1 || pattern[i] == pattern[j]) {
      i++;
      j++;
      n[i] = j;
    } else {
      j = n[j];
    }
  }
  return n;
}
int kmp(std::string &target, std::string &pattern) {
  int i = 0, j = 0;
  int pattern_size = pattern.length();
  std::vector<int> n(getNext(pattern));
  int s = pattern.length();
  while (i < target.length() && j < pattern.length()) {
    if (j == -1 || target[i] == pattern[j]) {
      i++;
      j++;
    } else {
      j = n[j];
    }
  }
  if (j == pattern.length()) {
    return i - j;
  } else {
    return -1;
  }
}
>>>>>>> dev:cxx/algorithm/common/src/kmp.cc
